package com.atwulidun.binarysorttree;

public class BinarySortTreeDemo {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
        BinarySortTree binarySortTree = new BinarySortTree();
        for (int j : arr) {
            binarySortTree.add(new Node(j));
        }
        binarySortTree.del(2);
        binarySortTree.del(10);
        binarySortTree.del(7);
        binarySortTree.del(3);
        binarySortTree.del(1);
        binarySortTree.del(9);
        binarySortTree.del(12);
        binarySortTree.del(5);
        binarySortTree.infixOrder();
    }
}

class BinarySortTree {
    private Node root;

    // 添加结点的方法
    public void add(Node node) {
        // 如果root为空，则把添加的结点作为root结点
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    // 查找要删除结点的方法
    public Node search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }

    public void infixOrder() {
        if (root == null) {
            System.out.println("二叉排序树为空，不能遍历！");
        } else {
            root.infixOrder();
        }
    }

    // 查找要删除结点的父结点的方法
    // 中序遍历的方法
    // 删除结点的方法，分为三种情况：
    // 1.待删除结点为叶子结点(父结点是否根结点)
    // 2.待删除结点有左右两个子树
    // 3.待删除结点只有左子树或者右子树(父结点是否根结点)
    public void del(int value) {
        if (root == null) {
            System.out.println("二叉排序树为空，不能删除！");
        } else {
            // 一、找到待删除的目标结点
            Node targetNode = search(value);
            // 二、如果找不到待删除的目标结点，直接返回即可
            if (targetNode == null) {
                return;
            }
            // 三、如果找到了待删除的目标结点，再继续找该结点的父结点
            Node parent = searchParent(value);
            // 四、以下开始分三种情况对目标结点进行讨论
            // 1.待删除结点为叶子结点
            if (targetNode.getLeft() == null && targetNode.getRight() == null) {
                // 若父结点为根结点
                if (parent == null) {
                    root = null;
                } else {
                    // 若父结点不为根结点，需要判断待删除结点是父结点的左子结点还是右子结点
                    // 因为父结点是根据子结点的value找到的，故直接判断当前结点是父结点的左还是右结点即可，不必再用value来判断
                    // 若当前结点为父结点的左子结点
                    if (parent.getLeft() == targetNode) {
                        parent.setLeft(null);
                    } else {
                        // 若当前结点为父结点的右子结点
                        parent.setRight(null);
                    }
                }
            } else if (targetNode.getLeft() != null && targetNode.getRight() != null) {
                // 2.待删除结点的左右子结点都不为空
                // 找待删除结点右子树中的最小值对应的结点，把最小值缓存下来后将该结点删掉，把待删除结点的值赋为缓存的值
//                int min = delRightTreeMin(targetNode);// 注意，这里传进去的是待删除结点的右结点，而不是待删除结点！！！！！！！
                int min = delRightTreeMin(targetNode.getRight());
                targetNode.setValue(min);
            } else {
                // 3.待删除的结点只有左子树或右子树
                // 待删除结点只有左子树
                if (targetNode.getLeft() != null) {
                    // 待删除结点的父结点为根结点
                    if (parent == null) {
                        root = targetNode.getLeft();
                    } else {
                        // 待删除结点的父结点不为根结点，还要判断待删除结点是其父结点的左结点还是右结点
                        // 如果待删除结点是其父结点的左结点
                        if (parent.getLeft() == targetNode) {
                            parent.setLeft(targetNode.getLeft());
                        } else {
                            // 如果待删除结点是其父结点的右结点
                            parent.setRight(targetNode.getLeft());
                        }
                    }
                } else {
                    // 待删除结点只有右子树
                    // 待删除结点的父结点为根结点
                    if (parent == null) {
                        root = targetNode.getRight();
                    } else {
                        // 待删除结点的父结点不为根结点，还要判断待删除结点是其父结点的左结点还是右结点
                        // 待删除结点为其父结点的左结点
                        if (parent.getLeft() == targetNode) {
                            parent.setLeft(targetNode.getRight());
                        } else {
                            // 待删除结点为其父结点的右结点
                            parent.setRight(targetNode.getRight());
                        }
                    }
                }
            }
        }
    }

    // 如果待删除结点的左右子结点都不为空，则需要找到其左子树中的最大值或其右子树中的最小值
    // 找待删除结点右子树中的最小值对应的结点，把最小值缓存下来后将该结点删掉，把待删除结点的值赋为缓存的值
    public int delRightTreeMin(Node node) {
        Node temp = node;
        while (temp.getLeft() != null) {
            temp = temp.getLeft();
        }
        // 找到最小值对应的结点后将最小值缓存下来
        int min = temp.getValue();
        // 将最小值对应的结点删除
        del(min);
        return min;
    }

    // 找待删除结点左子树中的最大值对应的结点，把最大值缓存下来后将该结点删掉，把待删除结点的值赋为缓存的值
    public int delLeftTreeMax(Node node) {
        Node temp = node;
        while (temp.getRight() != null) {
            temp = temp.getRight();
        }
        // 找到最小值对应的结点后将最小值缓存下来
        int max = temp.getValue();
        // 将最小值对应的结点删除
        del(max);
        return max;
    }
}

class Node {
    private int value;
    private Node left;
    private Node right;

    public Node(int value) {
        this.value = value;
    }

    // 添加结点的方法
    public void add(Node node) {
        // 如果node为空，直接返回
        if (node == null) {
            return;
        }
        // 判断新结点要加在当前结点的左边还是右边
        // 如果要添加的结点的值小于当前结点的值
        if (node.value < this.value) {
            // 如果当前结点的左结点为空，直接添加
            if (this.left == null) {
                this.left = node;
            } else {
                // 如果当前结点的左结点不为空，则递归添加
                left.add(node);
            }
        } else {
            // 如果要添加结点的值大于等于当前结点的值
            // 如果当前结点的右结点为空，直接添加
            if (this.right == null) {
                this.right = node;
            } else {
                // 如果当前结点的右结点不为空，则递归添加
                right.add(node);
            }
        }
    }

    // 查找要删除结点的方法
    // 分为三种情况进行讨论
    public Node search(int value) {
        // 如果要查找的值等于当前结点的值，直接返回当前结点
        if (value == this.value) {
            return this;
        } else if (value < this.value) {
            // 如果要查找的值小于当前结点的值
            // 如果当前结点的左结点为空，说明不存在要查找结点
            if (this.left == null) {
                return null;
            } else {
                // 如果当前结点的左结点不为空，则递归查找
                return left.search(value);
            }
        } else {
            // 如果要查找的值大于当前结点的值
            // 如果当前结点的右结点为空，说明要查找的结点不存在
            if (this.right == null) {
                return null;
            } else {
                // 如果当前结点的右结点不为空，则递归查找
                return right.search(value);
            }
        }
    }

    // 查找要删除结点的父结点的方法
    public Node searchParent(int value) {
        // 若当前结点的左结点或右结点的值等于要查找的值，那么直接返回当前结点即可
        if (left != null && left.value == value || right != null && right.value == value) {
            return this;
        }
        // 若要查找的值小于当前结点的值，则左递归查找
        if (value < this.value && left != null) {
            return left.searchParent(value);
        } else if (value >= this.value && right != null) {
            // 若要查找的值大于等于当前结点的值，则右递归查找
            return right.searchParent(value);
        } else {
            // 最后一种就是找不到的情况
            return null;
        }
    }

    // 中序遍历的方法
    public void infixOrder() {
        if (left != null) {
            left.infixOrder();
        }
        System.out.println(this);
        if (right != null) {
            right.infixOrder();
        }
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}

